package ljl.alg.hot100;

public class _53_max_sub_array {
    
    /*
     * 从头到尾扫：对于每个数，看看是当前数大，还是之前的数加当前数大
     * 同时记录一个全局最大值
     *
     * 居然做错了！
     *
     * */
    public int maxSubArray_wrong(int[] nums) {
        // 这个 max 初始化错了
        int max = -10001, cur = nums[0];
        for (int i = 1; i < nums.length; i++) {
            cur = Math.max(nums[i], nums[i] + cur);
            max = Math.max(cur, max);
        }
        return max;
    }
    
    public int maxSubArray3(int[] nums) {
        int max = nums[0], cur = max;
        for (int i = 1; i < nums.length; i++) {
            cur = Math.max(nums[i], nums[i] + cur);
            max = Math.max(cur, max);
        }
        return max;
    }
    
    public int maxSubArray2(int[] nums) {
        int prev = 0, max = nums[0];
        for (int num : nums) {
            // 最后一个 num 居然写成 prev 了
            // 真是个笨逼
            prev = Math.max(prev + num, num);
            max = Math.max(max, prev);
        }
        return max;
    }
    
    /**
     * 这是线段树？
     * 就是说有这么一个线段，每个线段有四个属性
     * iSum 总和
     * lSum 包含左端点的子区间最大值
     * rSum 同理
     * mSum 任意子区间最大值
     *
     * 然后把它一直分，分成只有一个元素，那这个元素四个属性值都为这个元素的值
     *
     * 然后两两合并子区间，最后得到原始线段的四个属性，取它的 mSum
     *
     * 如何合并？
     * iSum 为两个子区间 iSum 和
     * lSum 为 max(l.lSum, l.iSum + r.lSum)
     * rSum 同理
     * mSum = max(l.mSum, r.mSum, l.rSum + r.lSum)
     *
     * 看着繁琐，其实很清晰
     * 不知道哪个小天才想出来的
     *
     * @author 小天才
     */
    public int maxSubArray(int[] nums) {
        class Tree {
            int iSum, lSum, rSum, mSum;
            
            Tree(int iSum, int lSum, int rSum, int mSum) {
                this.iSum = iSum;
                this.lSum = lSum;
                this.rSum = rSum;
                this.mSum = mSum;
            }
            
            Tree() {
            }
            
            Tree fuck(int[] nums, int from, int to) {
                if (from == to) return new Tree(nums[from], nums[from], nums[from], nums[from]);
                int m = (from + to) / 2;
                Tree left = fuck(nums, from, m);
                Tree right = fuck(nums, m + 1, to);
                
                int iSum = left.iSum + right.iSum;
                int lSum = Math.max(left.lSum, left.iSum + right.lSum);
                int rSum = Math.max(right.rSum, right.iSum + left.rSum);
                int mSum = Math.max(left.mSum, Math.max(right.mSum, left.rSum + right.lSum));
                return new Tree(iSum, lSum, rSum, mSum);
            }
        }
        return new Tree().fuck(nums, 0, nums.length - 1).mSum;
    }
}
